1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// SPDX-FileCopyrightText: Copyright 2022 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later
#include "audio_core/renderer/nodes/node_states.h"
#include "common/logging/log.h"
namespace AudioCore::AudioRenderer {
void NodeStates::Initialize(std::span<u8> buffer_, [[maybe_unused]] const u64 node_buffer_size,
const u32 count) {
u64 num_blocks{Common::AlignUp(count, 0x40) / sizeof(u64)};
u64 offset{0};
node_count = count;
nodes_found.buffer.resize(count);
nodes_found.size = count;
nodes_found.reset();
offset += num_blocks;
nodes_complete.buffer.resize(count);
nodes_complete.size = count;
nodes_complete.reset();
offset += num_blocks;
results = {reinterpret_cast<u32*>(&buffer_[offset]), count};
offset += count * sizeof(u32);
stack.stack = {reinterpret_cast<u32*>(&buffer_[offset]), count * count};
stack.size = count * count;
stack.unk_10 = count * count;
offset += count * count * sizeof(u32);
}
bool NodeStates::Tsort(const EdgeMatrix& edge_matrix) {
return DepthFirstSearch(edge_matrix, stack);
}
bool NodeStates::DepthFirstSearch(const EdgeMatrix& edge_matrix, Stack& stack_) {
ResetState();
for (u32 node_id = 0; node_id < node_count; node_id++) {
if (GetState(node_id) == SearchState::Unknown) {
stack_.push(node_id);
}
while (stack_.Count() > 0) {
auto current_node{stack_.top()};
switch (GetState(current_node)) {
case SearchState::Unknown:
SetState(current_node, SearchState::Found);
break;
case SearchState::Found:
SetState(current_node, SearchState::Complete);
PushTsortResult(current_node);
stack_.pop();
continue;
case SearchState::Complete:
stack_.pop();
continue;
}
const auto edge_count{edge_matrix.GetNodeCount()};
for (u32 edge_id = 0; edge_id < edge_count; edge_id++) {
if (!edge_matrix.Connected(current_node, edge_id)) {
continue;
}
switch (GetState(edge_id)) {
case SearchState::Unknown:
stack_.push(edge_id);
break;
case SearchState::Found:
LOG_ERROR(Service_Audio,
"Cycle detected in the node graph, graph is not a DAG! "
"Bailing to avoid an infinite loop");
ResetState();
return false;
case SearchState::Complete:
break;
}
}
}
}
return true;
}
NodeStates::SearchState NodeStates::GetState(const u32 id) const {
if (nodes_found.buffer[id]) {
return SearchState::Found;
} else if (nodes_complete.buffer[id]) {
return SearchState::Complete;
}
return SearchState::Unknown;
}
void NodeStates::PushTsortResult(const u32 id) {
results[result_pos++] = id;
}
void NodeStates::SetState(const u32 id, const SearchState state) {
switch (state) {
case SearchState::Complete:
nodes_found.buffer[id] = false;
nodes_complete.buffer[id] = true;
break;
case SearchState::Found:
nodes_found.buffer[id] = true;
nodes_complete.buffer[id] = false;
break;
case SearchState::Unknown:
nodes_found.buffer[id] = false;
nodes_complete.buffer[id] = false;
break;
default:
LOG_ERROR(Service_Audio, "Unknown node SearchState {}", static_cast<u32>(state));
break;
}
}
void NodeStates::ResetState() {
nodes_found.reset();
nodes_complete.reset();
std::fill(results.begin(), results.end(), -1);
result_pos = 0;
}
u32 NodeStates::GetNodeCount() const {
return node_count;
}
std::pair<std::span<u32>::reverse_iterator, size_t> NodeStates::GetSortedResuls() const {
return {results.rbegin(), result_pos};
}
} // namespace AudioCore::AudioRenderer
|
